0148. 排序链表【中等】

• 1. 📝 题目描述
• 2. 🎯 s.1 - 归并排序

1. 📝 题目描述

• leetcode

给你链表的头结点 head，请将其按 升序 排列并返回 排序后的链表。

---

示例 1：

输入：head = [4,2,1,3]
输出：[1,2,3,4]

示例 2：

输入：head = [-1,5,3,4,0]
输出：[-1,0,3,4,5]

示例 3：

输入：head = []
输出：[]

---

提示：

• 链表中节点的数目在范围 [0, 5 * 10^4] 内
• -10^5 <= Node.val <= 10^5

进阶：你可以在 O(n log n) 时间复杂度和常数级空间复杂度下，对链表进行排序吗？

2. 🎯 s.1 - 归并排序

c

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode* merge(struct ListNode* l, struct ListNode* r) {
    struct ListNode dummy;
    struct ListNode* cur = &dummy;
    while (l && r) {
        if (l->val <= r->val) {
            cur->next = l;
            l = l->next;
        } else {
            cur->next = r;
            r = r->next;
        }
        cur = cur->next;
    }
    cur->next = l ? l : r;
    return dummy.next;
}

struct ListNode* sortList(struct ListNode* head) {
    if (!head || !head->next) return head;
    struct ListNode* slow = head;
    struct ListNode* fast = head->next;
    while (fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;
    }
    struct ListNode* mid = slow->next;
    slow->next = NULL;
    struct ListNode* left = sortList(head);
    struct ListNode* right = sortList(mid);
    return merge(left, right);
}

js

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var sortList = function (head) {
  if (!head || !head.next) return head
  // 找中点并断开
  let slow = head,
    fast = head.next
  while (fast && fast.next) {
    slow = slow.next
    fast = fast.next.next
  }
  const mid = slow.next
  slow.next = null
  // 递归排序左右两半
  const left = sortList(head)
  const right = sortList(mid)
  // 合并两个有序链表
  const dummy = new ListNode(0)
  let cur = dummy,
    l = left,
    r = right
  while (l && r) {
    if (l.val <= r.val) {
      cur.next = l
      l = l.next
    } else {
      cur.next = r
      r = r.next
    }
    cur = cur.next
  }
  cur.next = l || r
  return dummy.next
}

py

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def sortList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        if not head or not head.next:
            return head
        # 找中点并断开
        slow, fast = head, head.next
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
        mid = slow.next
        slow.next = None
        left = self.sortList(head)
        right = self.sortList(mid)
        # 合并
        dummy = ListNode(0)
        cur = dummy
        while left and right:
            if left.val <= right.val:
                cur.next = left
                left = left.next
            else:
                cur.next = right
                right = right.next
            cur = cur.next
        cur.next = left or right
        return dummy.next

• 时间复杂度：$O(n\log n)$，其中 $n$ 是链表的长度
• 空间复杂度：$O(\log n)$，递归调用栈的深度

算法思路：

• 用快慢指针找到链表中点，将链表断开为两半
• 递归对左右两半分别排序
• 将两个有序链表合并为一个有序链表